package com.xinwei.leetcode.数组;

import java.util.*;

// https://leetcode-cn.com/problems/3sum/
public class _15_三数之和 {
    public static List<List<Integer>> threeSum(int[] nums) {
        int len = nums.length;
        ArrayList<List<Integer>> lists = new ArrayList<>();
        if (len < 3) return lists;

        Arrays.sort(nums);
        for (int first = 0; first < len; first++) {
            // 为避免重复的，遇到相同的要跳过，得思考为什么这样可以避免重复的
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            int target = -nums[first];
            // 每一次更新 first 才需要更新third
            int third = len - 1;
            for (int second = first + 1; second < len; second++) {
                // 同样这个遇到相同的也得跳过
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }

                while (second < third && nums[second] + nums[third] > target) {
                    third--;
                }

                if (third == second) break;

                if (nums[second] + nums[third] == target) {
                    ArrayList<Integer> list = new ArrayList<>(3);
                    list.add(nums[first]);
                    list.add(nums[second]);
                    list.add(nums[third]);
                    lists.add(list);
                }
            }
        }
        return lists;
    }
}
